1. Field of the Invention
The present invention relates to an apparatus and method of matching symbols in a text image coding and decoding system, and more particularly, to an apparatus and method of reducing the number of matching operations and improving a quality/bit rate and a speed of a matching operation in a pattern matching based coding and decoding system.
2. Description of the Related Art
Generally, the JBIG2 standard, described in ITU-T T.88, defines a compression method for bi-level images, that is, images consisting of a single rectangular bit plane, with each pixel taking on one of just two possible colors. The JBIG2 standard only defines requirements for decoding a compliant bit stream corresponding to the images, and does not define a specific feature of an encoder design, but is flexible to many optimizations that can improve quality, compression, or speed of the encoder design.
In addition, the JBIG2 standard is the first international standard that provides for lossy, lossless, and lossy-to-lossless compression of the bi-level images, and supports multi-page images and model-based coding for text and halftones. The JBIG2 standard also permits compression ratios that are three to eight times better than previous standards, such as G3, G4, and JBIG1.
A bi-level document may contain one or more pages, and each page may contain text data, halftone data, and other data, such as line art or noise, as an input bi-level image. The JBIG2 encoder is expected to segment the input bi-level image into different regions, usually three regions, and to code each region separately using a different coding method.
FIG. 1 is a view illustrating a composite image as an input image to be decomposed into three regions in the JBIG2 standard, such as a text region, a halftone region, and a generic region.
The JBIG2 standard includes encoding the text region of the input image using a symbol dictionary. The input image is split into horizontal stripes. Each stripe is scanned in raster order to extract connected components (symbols). Each symbol extracted is compared with reference symbols in the symbol dictionary. If a match is found between the symbol of the input page and the reference symbols of the symbol dictionary, the symbol of the input image is encoded using the following information: its location offset relative to its preceding symbols, a dictionary index pointing to its best match with the reference symbol in the symbol dictionary, and a refinement of an encoded bitmap of the symbol of the input image. If the match is not found, a new symbol corresponding to the unmatched symbol of the input image is added to the symbol dictionary. This pattern matching based coding system is known as Pattern Matching and Substitution (PM&S).
The matching procedure generally operates by examining an error map, which is the bitwise exclusive-OR between the new symbol and a reference symbol of the dictionary. Before calculating the error map, the new symbol and the reference symbol are aligned appropriately with respect to each other, so that each pixel in one of the new symbol and the reference symbol can be mapped to the other one of the new symbol and the reference symbol. The error map is then evaluated using a distance metric. The distance metric is determined as follows.
Exclusive-OR (XOR) is used to computes the Hamming distance of the error map, that is, measure from the difference between the two symbols by the total number of pixels that are set in the error map.
Weighted Exclusive-OR (WXOR) is used to weigh the error pixels differently depending on the context in which the error occurs. Each error pixel contributes an amount that equals the number of error pixels in its 3*3 neighborhood. As a result, error pixels that occur in a cluster are more significant. FIG. 2 illustrates the WXOR operation where each white circle is an error pixel and the number inside the circle is the associated weight.
Weighted AND NOT (WAN) is used to weigh the error pixels in the same way as WXOR, but weights black-to-white errors differently from white-to-black ones.
Improved Weighted Exclusive-OR is used to let A and B be the symbols or bitmaps to be compared to generate metric differentiates between two error maps, E1 and E2. E1 contains pixels set in bitmap A but not in B, and E2 contains pixels set in B but not in A. The final error map is the sum of both.
Hausdoff distance is used to give a small effective weight to boundary pixels and to give a large effective weight to pixels that are not very near the boundary.
In order to cluster symbols into self-similar categories, a threshold is used to decide whether a match should be accepted or rejected. The result in each case is a binary decision, “match” or “no match”. A match is rejected if the error or distance exceeds the predefined threshold.
FIG. 2 is a diagram illustrating a weight exclusive or distance metric, for example, Weighted Exclusive-OR distance metric. Here, with the XOR distance metric, letters “c” and “o” are more similar than two versions of the letter “e.” However, with WXOR, a distance between the letters “e” is less than a distance between “c” and “o.” The XOR distance metric may lead to substitution errors unless a very tight threshold is defined. On the other hand, the very tight threshold may result in a big symbol dictionary, thereby reducing the bit rate. The WXOR distance metric can reduce the number of substitution errors in the encoding of a document without reducing the bit rate when using PM&S, however it has some computational overhead compared to the XOR metric.
Referring to FIG. 2, a view (a) illustrates A, B, and A+B to generate an error map produced by the comparison of two versions of the letter “e,” which results in an XOR distance of 29 and a WXOR distance of 75. A view (b) illustrates C, D, and C+D to generate an error map produced by the comparison of the letters “c” and “o” which results in an XOR distance of 23 and a WXOR distance of 131. Notice that WXOR distance assigns a greater error distance than XOR between the mismatched “c” and “o” symbols.
However, the above conventional matching process has disadvantages in that a processing time is increased, and that a bit rate is decreased.